#include<cstdio>//uncle-lu
#include<cstring>
#include<queue>
#include<algorithm>
template<class T>void read(T &x)
{
	x=0;int f=0;char ch=getchar();
	while(ch<'0'||ch>'9') { f|=(ch=='-'); ch=getchar(); }
	while(ch<='9'&&ch>='0') { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); }
	x = f ? -x : x;
	return ;
}

struct node{
	int v,next,val;
};
node edge[510];
int head[310],d[310],cnt,n,m;

struct HeapNode{
	int u,d;
	friend bool operator<(const HeapNode a,const HeapNode b){
		return a.d > b.d;
	}
	HeapNode(int uu,int dd){u = uu;d = dd;}
};
std::priority_queue<HeapNode>qu;

void init();
void add_edge(int,int,int);
void solution();
int find_min(int,int);

void init()
{
	memset(head,-1,sizeof(head));
	memset(d,0,sizeof(d));
	cnt=0;
	return ;
}

void add_edge(int x,int y,int val)
{
	cnt++;
	edge[cnt].v = y;
	edge[cnt].val=val;
	edge[cnt].next=head[x];
	head[x]=cnt;
	return ;
}

int find_min(int start,int end)
{
	memset(d,0x7f7f7f,sizeof(d));
	
	HeapNode now(start,0);
	d[start]=0;
	qu.push(now);
	while(!qu.empty())
	{
		now = qu.top();qu.pop();
		if(now.d != d[now.u])continue;
		for(int i=head[now.u];~i;i=edge[i].next)
			if(d[now.u] + edge[i].val < d[edge[i].v])
			{
				d[edge[i].v] = d[now.u] + edge[i].val;
				HeapNode next(edge[i].v,d[edge[i].v]);
				qu.push(next);
			}
	}

	return d[end];
}

void solution()
{
	read(n);read(m);
	int a,b,c;
	for(int i=1;i<=m;++i)
	{
		read(a);read(b);read(c);
		add_edge(a,b,c);
	}
	for(int i=1;i<=6;++i)
	{
		read(a);read(b);
		c = find_min(b,a);
		c = -c;
		printf("%d\n",c);
		add_edge(a,b,c);
	}
	return ;
}

int main()
{
	int T;
	read(T);
	for(int t=1;t<=T;++t)
	{
		init();
		solution();
	}
	return 0;
}
